#include <vector>
#include <string>
#include "RabinKarp.h"
using namespace std;

RabinKarp::RabinKarp(string wordToSearch) {
	word=wordToSearch; // слово, которое нужно найти
	p=31; // простое число для хэш-функции

	// массив степеней простого числа p
	pow_p.push_back(p);
	int len=word.length();
	for (int i=1; i<len; i++) {
		pow_p.push_back(pow_p[i-1]*p);
	}
}


// Вычисление хеша подстроки text[i..i+length-1], если посчитан хеш подстроки text[i-1..i+length-2]
int  RabinKarp::hash(int start, int length, int oldHash, string text) {
	int hash=0;
	if (start==0) {
		for (int i=start; i<start+length; i++) {
			hash+=pow_p[i-start]*text.at(i);
		}
		return hash;
	} else {
		hash=(oldHash-text.at(start-1)*p)/p+pow_p[length-1]*text.at(start+length-1);
	}

	return hash;
}


// алгоритм рабина-карпа, запускаемый для строки из файла
void RabinKarp::getNext(string text, vector<int>& matches, int beforeLength) {
	//cout<<"beforelength "<<beforeLength<<endl;
	int len=word.length();
	int wordHash=hash(0, len, 0, word);
	int subHash=0;
	int textLength=text.length();
	for (int i=0; i<textLength-len; i++) {
		subHash=hash(i, len, subHash, text);
		if (subHash==wordHash) {
			if (word==text.substr(i, len)) {
				matches.push_back(i+beforeLength);
			}
		}
	}
}

